#pragma once

#include <algorithm>
#include <vector>

namespace jianzhi_051
{

class Solution
{
public:
    int reversePairs(std::vector<int>& nums)
    {
        m_sorted.reserve(nums.size());
        return merge_sort(nums, 0, nums.size() - 1);
    }

private:
    int merge_sort(std::vector<int>& nums, int first, int last)
    {
        if (first >= last)
            return 0;

        int mid = (first + last) / 2;
        int count = merge_sort(nums, first, mid) + merge_sort(nums, mid + 1, last);

        int i = first;
        int j = mid + 1;
        while (i <= mid && j <= last) {
            if (nums.at(j) < nums.at(i)) {
                m_sorted.push_back(nums.at(j++));
                count += mid - i + 1;
            } else {
                m_sorted.push_back(nums.at(i++));
            }
        }
        for (; j <= last; ++j)
            m_sorted.push_back(nums.at(j));
        for (; i <= mid; ++i)
            m_sorted.push_back(nums.at(i));

        std::copy(m_sorted.cbegin(), m_sorted.cend(), nums.begin() + first);
        m_sorted.clear();
        return count;
    }

    std::vector<int> m_sorted;
};

}  /* namespace jianzhi_051 */
